///////////////////////////////////////////////////
/// tototoy Code
/// $Id: bytetree.h 26 2009-09-25 13:26:15Z tonyjobmails $
/// $Date: 2009-09-25 21:26:15 +0800 (五, 2009-09-25) $
/// $Author: tonyjobmails $
/// $Revision: 26 $
/// E-mail: tonyjobmails@gmail.com
/// filename: bytetree.h
/// function: 动态256叉树的实现
///////////////////////////////////////////////////

#ifndef __BYTETREE__H
#define __BYTETREE__H

#include "base.h"
#include "linklist.h"
#include "character.h"
#include "operate.h"

namespace tototoy
{
	using namespace base_type;
	using namespace base_fun;
	using namespace op;
	
	static const _uint_16 _NUM = 256;			/// 最大结点数
	
	///////////////////////////////////////////////////////////////////
	///////////////////////////////////////////////////////////////////
	/// 256树数据结构与相关操作定义
	///
	/// 动态256叉树结点结构
	template<typename _T>
	struct _node_byte
	{
		_node_byte()
		{
			parent_ptr = NULL;
			child_ptr = NULL;
			child_num = 0;
			linker = NULL;
		}
		typedef _node_byte<_T>* _child_pointer;
		_T data;					/// 数据部分
		_child_pointer parent_ptr;			/// 父结点
		_child_pointer *child_ptr;			/// 孩子结点
		_uint_16 child_num;				/// 孩子结点个数
		link_list<_node_byte<_T>* > *linker;		/// 结点数据为256树结点指针的链表(用于指向talking的可能性回答)
								/// 由于这个链表的数据为256树的结点指针，所以每当256树中有结点被
								/// delete的时候，要先对整个树进行遍历，把指向那个结点的所有指针置为NULL
								/// 重载delete操作符
		static void _delete(_node_byte<_T>* &op_data);	/// 删除结点
	};
	/// 重载<<操作符
	template<typename _T>
	std::ostream& operator << (std::ostream &output, _node_byte<_T>* &op_data)
	{
		if(op_data)
		{
			output << op_data->data;
		}
		return output;
	}
	///
	/// 用于清除256树结点指向链表中的一些结点的类<检测数据类型，检测条件类型>
	/// 只能保证检查每一个条件组中的第一个条件
	class action_clear_node_linker_node : public action<_node_byte<_character_type>*, _node_byte<_character_type>*>
	{
		public:
			action_clear_node_linker_node() {};
			~action_clear_node_linker_node() {};

			/// 实现方法是试删除每一个条件中包含的目标
			bool operator()(_node_byte<_character_type>* &data)
			{
				if(data->linker)
				{
					_check_condition_iter pos = this->check_condition_list.begin();
					for(; pos != this->check_condition_list.end(); ++pos)
					{
						_condition<_node_byte<_character_type>*> cond;
						if((*pos)->get_first_condition(cond))
							data->linker->delete_node(cond.cond_data);
					}
					return true;
				}
				return false;
			}
	};
	///
	/// 释放结点类型指针
	class action_free_tree_pointer : public action<_node_byte<_character_type>*, _node_byte<_character_type>*>
	{
		public:
			action_free_tree_pointer() {};
			~action_free_tree_pointer() {};

			bool operator()(_node_byte<_character_type>* &data)
			{
				if(this->pass_condition(data))
				{
					_node_byte<_character_type>::_delete(data);
					return true;
				}
				return false;
			}
	};
	///////////////////////////////////////////////////////////////////
	///////////////////////////////////////////////////////////////////


	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	//////////////////////////////////////////////////华丽的加粗分割线/////////////////////////////////////////////////////
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


	///////////////////////////////////////////////////////////////////
	///////////////////////////////////////////////////////////////////
	/// 动态256叉树类的声明
	class byte_tree
	{
		private:
			typedef link_list<_character_type> _link_list_type;
			typedef _node_byte<_character_type> _node_type;
			
		public:
			byte_tree();
			~byte_tree();

			_node_type* get_root()							/// 得到根结点
			{
				return this->root;
			}

			bool insert_chain(_link_list_type const &chain,
					_node_type* &leaf_node);				/// 插入一条链(理解为一个talking)
			bool insert_circle_chain(_link_list_type const &chain,
					_link_list_type const &rechain);			/// 插入一条回型链(理解为一个talk+answer)
			bool insert_rechain(_link_list_type const &chain,
					_link_list_type const &rechain);			/// 插入一条反链(理解为一个talk的answer)

			bool delete_chain(_link_list_type const &chain);			/// 查找删除一条链
			bool delete_node(_node_type const *node);				/// 删除一个结点
			bool delete_tree();							/// 删除整个树
			
			_node_type* search_chain(_link_list_type const &chain);			/// 查找一条链(返回最后一个结点指针)

			_link_list_type* export_chain(_node_type const *node);			/// 导出一个结点所表示的链(返回一个链表)

			static bool delete_chain(byte_tree *tree, _node_type *node);		/// 删除一个结点所在的链
			template<typename _T>
			static void traver_tree(_node_type* &node, op::action<_node_type*, _T> *operate = NULL);	/// 遍历整个树
			
		public:
			_node_type *root;							/// 根结点指针
			_uint_16 max_deep;							/// 树的深度(从0开始)
	};
	///////////////////////////////////////////////////////////////////
	///////////////////////////////////////////////////////////////////
};

#endif
